from typing import List
import functools
times = 0
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        global times
        from collections import deque
        queue = deque([amount])
        step = 0
        visited = set()
        while queue:
            n = len(queue)
            for _ in range(n):
                tmp = queue.pop()
                if tmp == 0:
                    print(times)
                    return step
                for coin in coins:
                    if tmp >= coin and tmp - coin not in visited:
                        times += 1
                        visited.add(tmp - coin)
                        queue.appendleft(tmp - coin)
            step += 1
        
        return -1

if __name__ == "__main__":
    coins = [1, 2, 5]
    amount = 11
    res = Solution().coinChange(coins, amount)
    print(res)